﻿// 0809train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;

/*
 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
二、题目解析
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，
这笔交易所能获得利润 = 4-2 = 2 。

示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 */


/*
 先写出k没有限制的情况
 */

int KFree(vector<int>& prices)
{
    //第i天没有股票，第i-1天就没有，第i-1天有，第i天卖出
    //dynamic_grid[i][0]=max(dynamic_grid[i-1][0],dynamic_grid[i-1][1]+prices[i])
    //第i天有股票，第i-1天就有，第i-1天没有，第i天买入
	//dynamic_grid[i][1]=max(dynamic_grid[i-1][1],dynamic_grid[i-1][0]-prices[i])

    int dp_size = prices.size();

    vector<vector<int>>dynamic_grid = vector<vector<int>>(dp_size, vector<int>(2));

    for (int i=0; i<dp_size; i++)
    {
        if (i-1==-1)
        {
            dynamic_grid[0][0] = 0;
            dynamic_grid[0][1] = -prices[0];
            continue;
        }

        dynamic_grid[i][0] = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1] + prices[i]);
        dynamic_grid[i][1] = max(dynamic_grid[i - 1][1], dynamic_grid[i - 1][0] - prices[i]);
    }

    return dynamic_grid[dp_size - 1][0];
    //KFree
}

int solve01(int k, vector<int>& prices)
{
    if (prices.empty())
    {
        return 0;
    }

    //举个具体的例子，4天内最多交易两笔，所以k==2相当于不受限制交易
    //直接返回上面k不受限制的解法
    if (k>=prices.size()/2)
    {
        return KFree(prices);
    }

    //第i天没有股票,第i-1天就没股票,今日卖出
    //dynamic_grid[i][l][0]=max(dynamic_grid[i-1][l][0],dynamic_grid[i-1][l][1]+prices[i])

    //第i天持有股票,第i-1天就有股票，今天刚买入
    //dynamic_grid[i][l][1]=max(dynamic_grid[i-1][l][1],dynamic_grid[i-1][l-1][0]-prices[i])

    //4个特殊情况
    //i==0 j==0 dynamic[0][l][0]=0 
    //i==0 j==1 dynamic[0][l][1]=-prices[0]
    //l==0 j==0 dynamic[i][0][0]=0 不能交易，利润为0
    //l==0 j==1 dynamic[i][0][1]=INT_MIN 不能交易，不可能有股票
    int limit = k + 1;
    int dp_size = prices.size();
    vector<vector<vector<int>>>dynamic_grid(dp_size, vector<vector<int>>(limit, vector<int>(2)));

    for (int i = 0; i < dp_size; i++)
    {
    	dynamic_grid[i][0][0] = 0;
    	dynamic_grid[i][0][1] = INT_MIN;
    }

    for (int i = 0; i < dp_size; i++)
    {
        for (int l=limit-1; l>=1;l--)
        {

            if (i-1==-1)
            {
                dynamic_grid[0][l][0] = 0;
                dynamic_grid[0][l][1] = -prices[0];
                continue;
            }


            //第i天没有股票,第i-1天就没股票,今日卖出
            int max_none = max(dynamic_grid[i - 1][l][0], dynamic_grid[i - 1][l][1] + prices[i]);
            dynamic_grid[i][l][0] = max_none;


            //第i天持有股票,第i-1天就有股票，今天刚买入
            int max_get = max(dynamic_grid[i - 1][l][1], dynamic_grid[i - 1][l - 1][0] - prices[i]);
            dynamic_grid[i][l][1] = max_get;

        }
    }

    //for (auto& outer_vec : dynamic_grid)
    //{
    //    for (auto& inner_vec : outer_vec)
    //    {
    //        cout << inner_vec[0] << ',' << inner_vec[1] << ' ';
    //    }
    //    cout << '\n';
    //}

    return dynamic_grid[dp_size - 1][k][0];
    //solve01
}


/*
 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。
你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

输入：prices = [7,1,5,3,6,4]
输出：7
 */

int solve02(vector<int>&prices)
{
    if (prices.empty())
    {
        return 0;
    }

    int dp_size = prices.size();

    vector<vector<int>>dynamic_grid = vector<vector<int>>(dp_size, vector<int>(2));

    for (int i=0; i<dp_size; i++)
    {
        if (i-1==-1)
        {
            dynamic_grid[0][0] = 0;
            dynamic_grid[0][1] = -prices[0];
            continue;
        }

        //3种情况, 第i-1天就没有/i-1天买了，今天出售/今天买入，今天售出
        int max_prev_0 = max(dynamic_grid[i - 1][0], dynamic_grid[i - 1][1] + prices[i]);
        dynamic_grid[i][0] = max(0, max_prev_0);

        //2种情况, 第i-1天就持有/i-1天没有，今天买入
        int max_prev_1 = max(dynamic_grid[i - 1][1], dynamic_grid[i - 1][0] - prices[i]);
        dynamic_grid[i][1] = max_prev_1;
        //for------
    }

    return dynamic_grid[dp_size - 1][0];
    //solve02
}


/*
 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1：
输入：prices = [3,3,5,0,0,3,1,4]
输出：6

 */
int solve03(vector<int>& prices)
{
    int limit = 2;//最多交易两笔
    int dp_size = prices.size();
    int limit_size = limit + 1;//保证dp方程能取到2

    vector<int>status_vec(2);
    vector<vector<int>>limit_vec(limit_size, status_vec);
    vector<vector<vector<int>>>dynamic_grid(dp_size, limit_vec);

    //边界情况k==0
    //dp[i][0][0]=0
    //dp[i][0][1]=INT_MIN

    for (int i=0; i<dp_size;i++)
    {
        dynamic_grid[i][0][0] = 0;
        dynamic_grid[i][0][1] = INT_MIN;
    }

    //边界情况i==0
    //dp[0][l][0]=0
    //dp[0][l][1]=-prices[0]

    //第i天没有，i-1无 / i-1有，i卖出
    //dynamic_grid[i][l][0]=max(dynamic_grid[i-1][l][0],dynamic_grid[i-1][l][1]+prices[i]);

    //第i天持有
    //dynamic_grid[i][l][1]=max(dynamic_grid[i-1][l][1],dynamic_grid[i-1][l-1][0]-prices[i]);
    for (int i=0; i<dp_size; i++)
    {
        for (int l=limit_size-1; l>=1; l--)
        {
            if (i-1==-1)
            {
                dynamic_grid[0][l][0] = 0;
                dynamic_grid[0][l][1] = -prices[0];
                continue;
            }
            dynamic_grid[i][l][0] = max(dynamic_grid[i - 1][l][0], dynamic_grid[i - 1][l][1] + prices[i]);
            dynamic_grid[i][l][1] = max(dynamic_grid[i - 1][l][1], dynamic_grid[i - 1][l - 1][0] - prices[i]);
        }
    }

    return dynamic_grid[dp_size - 1][limit_size - 1][0];
    //solve03
}

int main()
{
	{
        //prices = [3,3,5,0,0,3,1,4] 6
        vector<int>prices = { 3,3,5,0,0,3,1,4 };
        cout << solve03(prices);
        return 0;
	}

	{
        //输入：prices = [7, 1, 5, 3, 6, 4]
		//输出：7
        vector<int>prices = { 7, 1, 5, 3, 6, 4 };
        cout << solve02(prices);

        return 0;
	}

    {
        //k = 2, prices = [2,4,1] 
        //k = 2, prices = [3,2,6,5,0,3]
        vector<int>prices = { 3,2,6,5,0,3 };
        //cout << KFree(prices);
        int k = 2;
        cout << solve01(k, prices);
        return 0;
    }

    //k = 2,prices = [2, 4, 1]
    int k = 2;
    vector<int>prices = { 2, 4, 1 };
    cout << solve01(k, prices);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
